package 剑指offer;

public class _17打印从1到最大的n位数 {
	/**
	 * 
	 *@time 2021年1月7日下午4:40:09
	 * 
	 *@param n
	 *@return int[]
	 *
	 *@see不考虑大数越界问题
	 */
	public int[] printNumbers1(int n) {
		int num=(int) Math.pow(10, n);
		int nums[]=new int[num-1];
		for (int i = 0; i < num-1; i++) {
			nums[i]=i+1;
		}
		return nums;		
	}
	/**
	 * 
	 *@time 2021年1月7日下午4:41:59
	 * 
	 *@param n
	 *@returnint[]
	 *
	 *@see 考虑大数越界问题
	 *问题转换成数字排列的解法 ，然后使用递归
	 */
	int res[];
	char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
	int count=0,start,nine=0;
	public int[] printNumbers2(int n) {		
		if(n<=0) return null;
		num=new char[n];
		start=n-1;
		res=new int[(int) Math.pow(10, n)];
		dfs(n, 0);
		return res;		
	}
	public void dfs(int lenth,int index) {
		if(index==lenth) {
			String s=String.valueOf(num).substring(start);
			if(!s.equals("0")) res[count++]=Integer.parseInt(s);
			if(lenth-start==nine) start--;
			return;
		}
		for (char c : loop) {
			if(c=='9') nine++;
			num[index]=c;
			dfs(lenth, index+1);
		}	
	}
}

class a {
    int[] res;
    int nine = 0, count = 0, start, n;
    char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
    public int[] printNumbers(int n) {
        this.n = n;
        res = new int[(int)Math.pow(10, n) - 1];
        num = new char[n];
        start = n - 1;
        dfs(0);
        return res;
    }
    void dfs(int x) {
        if(x == n) {
            String s = String.valueOf(num).substring(start);
            if(!s.equals("0")) res[count++] = Integer.parseInt(s);
            if(n - start == nine) start--;
            return;
        }
        for(char i : loop) {
            if(i == '9') nine++;
            num[x] = i;
            dfs(x + 1);
        }
        nine--;
    }
}


